package src.leetcode.dp.medium_0494;

public class findTargetSumWays {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3));
    }
}

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int newTarget = sum - (sum - target) / 2;
        if(sum - target < 0 || (sum - target) % 2 != 0) return 0;

        int []dp = new int[newTarget + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int j = newTarget; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[newTarget];
    }
}

